package com.example.leetcode.prcatice;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个单链表 L 的头节点 head ，单链表 L 表示为：
 *
 * <p> L0 → L1 → … → Ln-1 → Ln  请将其重新排列后变为：
 *
 * <p>L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reorder-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Test143 {

    public void reorderList(ListNode head) {

        if (head == null){
            return;
        }
        ListNode pre = head;
        ListNode newHead = new ListNode();
        ListNode tail = newHead;
        List<ListNode> list = new ArrayList<>();
        while (pre != null){
            list.add(pre);
            pre = pre.next;
        }
        int size = list.size();
        for (int i =0;i<=size/2;i++){
            tail.next = list.get(i);
            int len = size - 1 - i;
            tail = list.get(i);
            if (len > i){
                // 说明不是用一个
                tail.next = list.get(len);
                tail = list.get(len);
            }
        }
        tail.next = null;
    }
}

class Demo143{
  public static void main(String[] args) {
    ListNode head = new ListNode(1);
    head.next = new ListNode(2);
    head.next.next = new ListNode(3);
    head.next.next.next = new ListNode(4);
    head.next.next.next.next = new ListNode(5);
    Test143 t = new Test143();
    t.reorderList(head);
    while (head!= null){
      System.out.println("val="+head.val);
      head = head.next;
    }
  }
}